package com.example.algo.findMedianSortedArrays;

/**
 * 寻找两个有序数组的中位数
 * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
 * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * <p>
 * 示例 1:
 * nums1 = [1，3]
 * nums2 = [2]
 * 则中位数是 2.0
 * <p>
 * 示例 2:
 * nums1 = [1，2]
 * nums2 = [3，4]
 * 则中位数是 (2 + 3)/2 = 2.5
 */
public class Solution {

    public static void main(String[] args) {
        int[] nums1 = {1, 3, 7};
        int[] nums2 = {5, 6, 8, 9};
        System.out.println(findMedianSortedArrays(nums1, nums2));
    }

    /*
    题解

    中位数的作用：将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素

    A、B 是集合，m，n 是集合的元素个数，i，j 是将结合 A，B 分成 2 段随机选择的位置（元素所在的位置不是数组下标）
    A 对应 m，i  B 对应 n，j

    由于 A 中有 m 个元素， 所以我们有 m+1 种划分的方法（i = 0 ∼ m）
    A 集合被 i 分割之后分为 left_A、 right_A 两部分，分割后 len(left_A) = i，len(right_A) = m -i;

    B 集合被 j 分割之后分为 left_B、 right_B 两部分
    将 left_A,left_b 合并成 left_part，right_A,right_B 合并成 right_part 两部分
    如果可以确定下面2个条件
    1、len(left_part) = len(right_part)
    2、max(left_part) <= min(right_part)
    既然我们已经将 {A,B} 中的所有元素划分为相同长度的两个部分，且其中一部分中的元素总是大于另一部分中的元素
    那么：median = (max(left_part) + min(right_part)) / 2
    要确保上面 2 个条件成立，我们只需要保证
    1、i + j = m - i + n - j 或 i + j = m - i + n - j + 1，如果 n >= m，0 < i < m 所以 j = (m + n + 1) / 2 - i
        PS:1 的公式解析
            当 m = 6，n = 6，i = 2，j = 3 时，划分之后 left_part = right_part 相同
            i + j = m - i + n - j
            当 m = 5，n = 6，i = 3，j = 3时，划分之后 left_part < right_part 相同
            i + j = m - i + n - j + 1
        PS:2 为了简化，假设 B[j - 1]、A[i]、A[i - 1]、B[j] 总是存在，即使出现 i = 0、i = m、j = 0、j = n 这样的临界条件
            将在下面讨论如何处理这些临界条件
        PS:3 为什么 n >= m？由于0 <= i <= m 且 j = (m + n + 1) / 2 - i，这里必须要保证 j 不能为负数，如果 n < m，
            那么 j 可能为负数，这样将会出现错误的答案。
    2、B[j - 1] <= A[i] 并且 A[i - 1] <= B[j]

    我们需要做的就是在 0 ~ m 之间找寻目标对象 i，以使：B[j - 1] <= A[i] 并且 A[i - 1] <= B[j]，其中 j = (m + n + 1) / 2 -i

    可以按照以下步骤来进行二叉树搜索

    1、设 imin = 0，imax = m，然后开始在 [imin, imax] 中搜索
    2、令 i = (imin + imax) / 2，j = (m + n + 1) / 2 - i
    3、现在我们有len(left_part) = len(right_part)。而且只会遇到下面的三种情况：
        1）B[j - 1] <= A[i] 并且 A[i - 1] <= B[j]，这是最优情况，意味着我们已经找到 i 的位置，所以可以结束寻找
        2）B[j - 1] > A[i]，这意味着 A[i] 太小，需要增大 i 的值以使 B[j - 1] <= A[i]，根据上面公式 i 增大 j 就会变小，并转到第2步
        3）A[i - 1] > B[j]，这意味着 A[i - 1] 太大，需要减小 i 的值以使 A[i - 1] <= B[j]

    当找到目标对象 i 时，中位数为 median：
    1、当 m + n 为奇数的时候，median = max(A[i - 1], B[j - 1])
    2、当 m + n 为偶数的时候，median =(max(A[i - 1], B[j - 1]) + min(A[i], B[j])) / 2


    现在考虑临界值i = 0，i = m，j = 0，j = n，此时 A[i - 1]，B[j - 1]，A[i]，B[j] 可能不存在，那么我们只需要检查
    B[j - 1] <= A[i] 并且 A[i - 1] <= B[j] 这两个条件中的一个（或不需要检查）。
    举个例子：如果 i = 0，那么 A[i - 1] 不存在，那么就不需要检查 A[i - 1] <= B[j] 是否成立，所以需要做的是：
    在[0, m] 范围内搜索并找到 i，以使（j = 0 or i = m or B[j - 1] <= A[i]）或（i = 0 or j = n or A[i - 1] <= B[j] ）
    这些临界情况出现，在循环搜索中只会遇到下面三种情况：
        1）（j = 0 or i = m or B[j - 1] <= A[i]）或（i = 0 or j = n or A[i - 1] <= B[j] ），这意味着 i 是完美的，可以结束寻找
        2）j > 0 and i < m and B[j - 1] > A[i] 这意味着 i 太小需要增大 i 的值
        3）i > 0 and j < n and A[i - 1] > B[j] 这意味着 i 太大需要减小 i 的值
        PS: j > 0 and i < m，i > 0 and j < n 的推导如下（m，n，i 可以代入实际数值推导）
            m <= n，i < m，假设 m = n，i = m              m <= n，i < m
            ==> j = (m + n + 1) / 2 - i
            ==> j > (m + n + 1) / 2 - m
            ==> j >= (2m + 1) / 2 - m
            ==> j >= 0

            m <= n，i > 0
            ==> j = (m + n + 1) / 2 - i
            ==> j < (m + n + 1) / 2
            ==> j <= (2n + 1) / 2
            ==> j <= n
        所以，在情况 2 和 3中，我们不需要检查 j > 0 或是 j < n 是否成立。

     */


    /**
     * 时间复杂度 O(log(min(m,n))) 首先查找的区间是{0,m}，而该区间在每次查找之后都会减少为原来的一半。
     *      所以只需要执行 log(m) 次循环，由于在每次循环内都进行常量次数的操作，所以时间复杂度为 O(log(m))，
     *      由于 m <= n，所以时间复杂度为 O(log(min(m,n)))
     * @param A
     * @param B
     * @return
     */
    public static double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length, n = B.length;
        // 先将两个数组转换位置，转换成 m <= n 的形式
        if (m > n) {
            int[] temp = A;
            A = B;
            B = temp;

            int tmp = m;
            m = n;
            n = tmp;
        }

        int imin = 0, imax = m, halfLen = (m + n + 1) / 2;

        while (imin <= imax) {
            // 使用二分查找方法
            int i = (imin + imax) / 2;
            int j = halfLen - i;

            // B 集合 left 的值 大于 A 集合 right 的值，说明i j 的位置没选对
            if (i < imax && B[j - 1] > A[i]) {
                // i 的位置太小了
                imin = i + 1;
            }
            // A 集合 left 的值 大于 B 集合 right 的值，说明i j 的位置没选对
            else if (i > imin && A[i - 1] > B[j]) {
                // i 的位置太大了
                imax = i - 1;
            } else {
                // 判断 i 是临界值 0 或 m 的问题

                // 左边最大数 只能在 A[i - 1] 和 B[j - 1] 中选择
                int maxLeft = 0;
                if (i == 0) {
                    maxLeft = B[j - i];
                } else if (j == 0) {
                    maxLeft = A[i - 1];
                } else {
                    maxLeft = Math.max(A[i - 1], B[j - 1]);
                }
                // 如果结果集的长度是奇数，可以直接返回左边最大值就是中心数
                if ((m + n) % 2 == 1) {
                    return maxLeft;
                }

                // 右边最小数
                int minRight = 0;
                if (i == m) {
                    minRight = B[j];
                } else if (j == n) {
                    minRight = A[i];
                } else {
                    minRight = Math.min(A[i], B[j]);
                }

                // 如果结果集的长度是偶数，就用 left_part 最大值和 right_part 最小值相加求平均数
                return (maxLeft + minRight) / 2.0;
            }
        }

        return 0;
    }

}
